import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-09-12
 * Time: 21:20
 */
public class find_Anagrams {
    public static List<Integer> findAnagrams1(String s, String p) {
        int count = 0;
        char[] charArray = s.toCharArray();
        List<Integer> ret = new ArrayList<>();
        HashMap<Character, Integer> hashMap1 = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            hashMap1.put(p.charAt(i), hashMap1.getOrDefault(p.charAt(i), 0) + 1);
        }
        HashMap<Character, Integer> hashMap2 = new HashMap<>();
        for (int right = 0, left = 0; right < charArray.length; right++) {
            //进窗口
            Integer df = hashMap2.getOrDefault(charArray[right], 0);

            hashMap2.put(charArray[right], df + 1);
            if (hashMap1.containsKey(charArray[right])) {
                if (df + 1 <= hashMap1.get(charArray[right])) {
                    count++;
                }
            }
            while (right - left + 1 > p.length()) {
                //判断
                int n = hashMap2.get(charArray[left]);

                if (hashMap1.containsKey(charArray[left])) {
                    if (n <= hashMap1.get(charArray[left])) {
                        count--;
                    }
                }
                hashMap2.put(charArray[left], n - 1);
                left++;
            }
            if (count == p.length()) {
                ret.add(left);
            }

        }
        return ret;
    }

    public List<Integer> true_findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26]; // 统计字符串 p 中每⼀个字符出现的个数
        for (char ch : p) hash1[ch - 'a']++;
        int[] hash2 = new int[26]; // 统计窗⼝中每⼀个字符出现的个数
        int m = p.length;
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            // 进窗⼝ + 维护 count
            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            if (right - left + 1 > m) // 判断
            {
                char out = s[left++];
                // 出窗⼝ + 维护 count
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            // 更新结果
            if (count == m) ret.add(left);
        }
        return ret;
    }
    public static List<Integer> findAnagrams(String s, String p){


        int count = 0;
        char[] charArray = s.toCharArray();
        List<Integer> ret = new ArrayList<>();


        HashMap<Character, Integer> hashMap1 = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            hashMap1.put(p.charAt(i), hashMap1.getOrDefault(p.charAt(i), 0) + 1);
        }

        HashMap<Character, Integer> hashMap2 = new HashMap<>();

        for (int right = 0, left = 0; right < charArray.length; right++) {
            //进窗口
            char right_char=charArray[right];
            Integer df = hashMap2.getOrDefault(right_char, 0);

            hashMap2.put(right_char, df + 1);
            if (hashMap1.containsKey(charArray[right])) {

                Integer i = hashMap1.get(charArray[right]);
                if (df + 1 == i) {
                    count++;
                }
            }

            while (right - left + 1 > p.length()) {
                //判断

                int n = hashMap2.get(charArray[left]);

                if (hashMap1.containsKey(charArray[left])) {

                    int m=hashMap1.get(charArray[left]);

                    if (n == hashMap1.get(charArray[left])) {
                        count--;
                    }
                }


                hashMap2.put(charArray[left], n - 1);
                left++;
            }

            if (count == hashMap1.size()) {
                ret.add(left);
            }

        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(findAnagrams("baa", "aa"));
    }
}
